// -----------------------------------------------------------------------------
// Copyright (c) 2014-2024 All rights reserved
// -----------------------------------------------------------------------------
// Author 		: HiDark 1173296519@qq.com
// File   		: sqrt_uDW.sv
// Create 		: 2024-01-03 15:47:14
// Description	: N bit square root 
// Editor 		: tab size (4)
// -----------------------------------------------------------------------------
module sqrt_u32 #(
    parameter DW = 32
    )(
    input               clk,
    input               rst_n,
    input               vld_in,
    input   [DW-1:0]    x,

    output              vld_out,
    output  [DW/2:0]    y
);
//Total number of iterations, half the input bit width
localparam ITERA_NUM = DW/2;

reg [$clog2(ITERA_NUM)-1:0]  cnt;//Record the number of iterations
reg [DW-1:0]  din_reg;//Save input data
reg [DW-1:0]  rem;//Remainder
reg [DW/2-1:0]  quo;//Quotient
reg         busy;//Under Calculation

//-----------------------------------------------------------------
// Calculation
//-----------------------------------------------------------------

//4a+1,left shift 2bits and add 1
wire [DW-1:0]  subtrahend = {{(DW/2-3){1'b0}},quo[DW/2-1:0],2'b01};
//Subtracted number
wire [DW-1:0]  minuend    = {rem[DW-3:0],din_reg[DW-1:DW-2]};
//Comparison of remainder  
wire           cmp        = (minuend>=subtrahend)?1'b1:1'b0;
//cmp decides whether to subtract
wire [DW-1:0]  rem_next   = minuend-({DW{cmp}}&subtrahend);

always @(posedge clk or negedge rst_n) begin
    if(~rst_n) begin
        busy        <= 0;
        cnt         <= ITERA_NUM-1;
        din_reg     <= 0;
        rem         <= 0;
        quo         <= 0;
    end else begin case(busy)
        1'b0:begin
            busy    <= vld_in;
            cnt     <= ITERA_NUM-1;
            din_reg <= x;
            rem     <= 0;
            quo     <= 0;        
        end
        1'b1:begin
            busy    <= |cnt;// cnt == 0 ==> calculation finished
            cnt     <= cnt - 1;
            din_reg <= {din_reg[DW-3:0],2'b0}; // left shift 2bits
            rem     <= rem_next;
            quo     <= {quo[DW/2-2:0],cmp}; // left shift 1bit     
        end 
    endcase
    end   
end
assign vld_out = ~busy;
assign y = quo;

endmodule


